package Random_Problem.Day_0204;

/**
 * @author zxc
 * @date 2023/02/04 08:59
 **/

import java.util.List;

/**
 * 题目 ：钥匙和房间
 * 题目详述 ：
 * 有 n 个房间，房间按从 0 到 n - 1 编号。
 * 最初，除 0 号房间外的其余所有房间都被锁住。你的目标是进入所有的房间。
 * 然而，你不能在没有获得钥匙的时候进入锁住的房间。
 * 当你进入一个房间，你可能会在里面找到一套不同的钥匙，每把钥匙上都有对应的房间号，即表示钥匙可以打开的房间。你可以拿上所有钥匙去解锁其他房间。
 * 给你一个数组 rooms 其中 rooms[i] 是你进入 i 号房间可以获得的钥匙集合。如果能进入 所有 房间返回 true，否则返回 false。
 *
 * 提示：
 * n == rooms.length
 * 2 <= n <= 1000
 * 0 <= rooms[i].length <= 1000
 * 1 <= sum(rooms[i].length) <= 3000
 * 0 <= rooms[i][j] < n
 * 所有 rooms[i] 的值 互不相同
 *
 */
public class CanVisitAllRooms {
    /**
     * 思路 ：
     * 当 xx 号房间中有 yy 号房间的钥匙时，我们就可以从 xx 号房间去往 yy 号房间。
     * 如果我们将这 nn 个房间看成有向图中的 nn 个节点，那么上述关系就可以看作是图中的 xx 号点到 yy 号点的一条有向边。
     * ===》
     * 这样一来，问题就变成了给定一张有向图，询问从 0号节点出发是否能够到达所有的节点。
     *
     * @param rooms
     * @return
     */
    // 图的深度优先搜索 :
    public boolean canVisitAllRooms(List<List<Integer>> rooms) {
        int len = rooms.size();
        // 使用dp辅助数组，来记录当前房间是否已经被解锁;
        boolean[] dp = new boolean[len];
        // 变量sum，用来记录已经解锁的房间数;
        int sum = 0;
        // 递归遍历所有能够到达的图节点;
        // 初始化 ：由于一开始只有0号房间是解锁的，所以选择去遍历0号房间;
        sum = dfs(rooms , dp , sum , 0);
        return sum == len;
    }

    private int dfs(List<List<Integer>> rooms, boolean[] dp, int sum, int index) {
        // （1）当前图节点置为true，代表其已经被解锁 && 被遍历过;
        dp[index] = true;
        sum++;
        // （2）遍历当前图节点，获取当前房间所存放的所有钥匙;
        for (Integer roomKey : rooms.get(index)) {
            // （3）若是当前钥匙所对应的房间还未被解锁;
            if(!dp[roomKey]){
                sum = dfs(rooms, dp , sum , roomKey);
            }
        }
        return sum;
    }
}
